package com.xyhuo.leetcode.december;

import java.util.Arrays;

/**
 * 最接近的三数之和
 * https://leetcode.cn/problems/3sum-closest/
 *
 * @time 2023/12/7
 */
public class ThreeSumClosest {

//    public static void main(String[] args) {
//        ThreeSumClosest tsc = new ThreeSumClosest();
//        int[] nums = {1, 1, 1, 0};
//        int i = tsc.threeSumClosest(nums, 100);
//        System.out.println(i);
//    }

    private long bt = Integer.MAX_VALUE;
    private long ans = 0;

    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int len = nums.length;
        for (int i = 0; i < len - 2; i++) {
            int left = i + 1, right = len - 1;
            while (true) {
                if (left >= right) {
                    break;
                }
                long tmp = nums[i] + nums[left];
                tmp += nums[right];
                if (tmp > target) {
                    right--;
                } else if (tmp < target) {
                    left++;
                } else {
                    return target;
                }
                long bet = Math.abs(tmp - target);
                if (bet < bt) {
                    bt = bet;
                    ans = tmp;
                }
            }
        }
        return (int) ans;
    }
}
